<!DOCTYPE html>
            
<HTML>
<HEAD>
<meta name="booktitle" content="Developing Applications With Objective Caml" >
 <meta charset="ISO-8859-1"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
<META name="GENERATOR" content="hevea 1.05-7 of 2000-02-24">
<META NAME="Author" CONTENT="Christian.Queinnec@lip6.fr">
<LINK rel=stylesheet type="text/css" href="videoc-ocda.css">
<script language="JavaScript" src="videoc.js"><!--
//--></script>
<TITLE>
 Type declarations and pattern matching
</TITLE>
</HEAD>
<BODY class="regularBody">
<A HREF="book-ora015.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora017.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2> Type declarations and pattern matching</H2>
<A NAME="@concepts55"></A>
<A NAME="@concepts56"></A>
Although Objective CAML's predefined types permit the construction of data
structures from tuples and lists, one needs to be able to define new
types to describe certain data structures. In Objective CAML, type declarations
are recursive and may be parameterized by type variables, in the same vein
as the type <I>'a list</I> already encountered. Type inference takes
these new declarations into account to produce the type of an expression.
The construction of values of these new types uses the constructors
described in their definition. A special feature of languages in the ML
family is pattern matching. It allows simple access to the
components of complex data structures. A function definition most often
corresponds to pattern matching over one of its parameters, allowing the
function to be defined by cases.<BR>
<BR>
First of all we present pattern matching over the predefined types, and
then go on to describe the various ways to declare structured types and how
to construct values of such types, as well as how to access their
components through pattern matching.<BR>
<BR>
<A NAME="toc14"></A>
<H3> Pattern matching</H3>
<A NAME="subsec-filtrage"></A>
<A NAME="@concepts57"></A>
<A NAME="@concepts58"></A>
<A NAME="@concepts59"></A>
<A NAME="@concepts60"></A>
A pattern is not strictly speaking an Objective CAML expression. It's more like
a correct (syntactically, and from the point of view of types) arrangement
of elements such as constants of the primitive types (<I>int</I>,
<I>bool</I>, <I>char</I>, ..), variables, constructors, and the symbol
<B>_</B> called the wildcard pattern. Other symbols are used in
writing patterns. We will introduce them to the extent needed.<BR>
<BR>
Pattern matching applies to values. It is used to recognize the form of
this value and lets the computation be guided accordingly,
associating with each pattern an expression to compute.
<A NAME="@fonctions75"></A>
<A NAME="@fonctions76"></A>


<H3> Syntax </H3> <HR>


<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><B>match</B>  <I>expr</I>  <B>with</B></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><B>|</B> <I>p</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB>  -&gt; <I>expr</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>:</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><B>|</B> <I>p</I><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB>  -&gt; <I>expr</I><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB></TD>
</TR></TABLE>



<HR>


The expression <I>expr</I> is matched sequentially to the various patterns
<I>p</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB>, ..., <I>p</I><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB>. If one of the patterns (for example
<I>p</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB>) is consistent with the value of <I>expr</I> then the
corresponding computation branch (<I>expr</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB>) is evaluated. The
various patterns <I>p</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB> are of the same type. The same goes for
the various expressions <I>expr</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB>. The vertical bar preceding the
first pattern is optional.<BR>
<BR>

<H4> Examples</H4>
Here are two ways to define by pattern matching a function <TT>imply</TT>
of type <I>(bool * bool)</I>  -&gt; bool implementing logical
implication. A pattern which matches pairs has the form <CODE>( , )</CODE>.<BR>
<BR>
The first version of <TT>imply</TT> enumerates all possible cases, as a
truth table would:


<PRE><BR># <B>let</B><CODE> </CODE>imply<CODE> </CODE>v<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>v<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT><B>true</B><CODE>,</CODE><B>true</B><TT>)</TT><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>true</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT><B>true</B><CODE>,</CODE><B>false</B><TT>)</TT><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>false</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT><B>false</B><CODE>,</CODE><B>true</B><TT>)</TT><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>true</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT><B>false</B><CODE>,</CODE><B>false</B><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><B>true</B>;;<BR><CODE>val imply : bool * bool -&gt; bool = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
By using variables which group together several cases, we obtain a more
compact definition.


<PRE><BR># <B>let</B><CODE> </CODE>imply<CODE> </CODE>v<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>v<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT><B>true</B><CODE>,</CODE>x<TT>)</TT><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE>x<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT><B>false</B><CODE>,</CODE>x<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><B>true</B>;;<BR><CODE>val imply : bool * bool -&gt; bool = &lt;fun&gt;</CODE><BR>

</PRE>

These two versions of <TT>imply</TT> compute the same function. That is,
they return the same values for the same inputs.<BR>
<BR>

<H4> Linear pattern</H4>
A pattern must necessarily be <EM>linear</EM>, that is, no given variable can
occur more than once inside the pattern being matched. Thus, we might have 
hoped to be able to write:


<PRE><BR># <B>let</B><CODE> </CODE>equal<CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>c<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT>x<CODE>,</CODE>x<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><B>true</B><BR><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>x<CODE>,</CODE>y<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><B>false</B>;;<BR><CODE>Characters 35-36:</CODE><BR><CODE>This variable is bound several times in this matching</CODE><BR>

</PRE>

But this would have required the compiler to know how to carry out equality
tests. Yet this immediately raises numerous problems.
If we accept physical equality between values, we get a system which is too
weak, incapable of recognizing the equality between two occurrences of the
list <CODE>[</CODE><CODE>1</CODE>;<CODE> </CODE><CODE>2</CODE><CODE>]</CODE>, for example. If we decide to use structural
equality, we run the risk of having to traverse, ad infinitum, circular
structures. Recursive functions, for example, are circular structures, but
we can construct recursive, hence circular, values which are not functions
as well (see page <A HREF="book-ora016.html#decl_rec">??</A>). <BR>
<BR>

<H4> Wildcard pattern</H4>
<A NAME="@concepts61"></A>
<A NAME="@concepts62"></A>
<A NAME="@fonctions77"></A>
The symbol <B>_</B> matches all possible values. It is called a wildcard
pattern. It can be used to match complex types. We use it, for example,
to further simplify the definition of the function <TT>imply</TT>: 


<PRE><BR># <B>let</B><CODE> </CODE>imply<CODE> </CODE>v<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>v<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT><B>true</B><CODE>,</CODE><B>false</B><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><B>false</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>true</B>;;<BR><CODE>val imply : bool * bool -&gt; bool = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
A definition by pattern matching must handle the entire set of possible
cases of the values being matched. If this is not the case, the compiler
prints a warning message:


<PRE><BR># <B>let</B><CODE> </CODE>is_zero<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>n<CODE> </CODE><B>with</B><CODE> </CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>true</B><CODE> </CODE>;;<BR><CODE>Characters 17-40:</CODE><BR><CODE>Warning: this pattern-matching is not exhaustive.</CODE><BR><CODE>Here is an example of a value that is not matched:</CODE><BR><CODE>1</CODE><BR><CODE>val is_zero : int -&gt; bool = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
Indeed if the actual parameter is different from <CODE>0</CODE> the function
doesn't know what value to return. So the case analysis can be completed
using the wildcard pattern.


<PRE><BR># <B>let</B><CODE> </CODE>is_zero<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>n<CODE> </CODE><B>with</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>true</B><BR><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>false</B><CODE> </CODE>;;<BR><CODE>val is_zero : int -&gt; bool = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
If, at run-time, no pattern is selected, then an exception is raised.
Thus, one can write:


<PRE><BR># <B>let</B><CODE> </CODE>f<CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>x<CODE> </CODE><B>with</B><CODE> </CODE><CODE>1</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>3</CODE><CODE> </CODE>;;<BR><CODE>Characters 11-30:</CODE><BR><CODE>Warning: this pattern-matching is not exhaustive.</CODE><BR><CODE>Here is an example of a value that is not matched:</CODE><BR><CODE>0</CODE><BR><CODE>val f : int -&gt; int = &lt;fun&gt;</CODE><BR># f<CODE> </CODE><CODE>1</CODE><CODE> </CODE>;;<BR><CODE>- : int = 3</CODE><BR># f<CODE> </CODE><CODE>4</CODE><CODE> </CODE>;;<BR><CODE>Uncaught exception: Match_failure("", 11, 30)</CODE><BR>

</PRE>

<A NAME="@fonctions78"></A>
The <TT>Match_Failure</TT> exception is raised by the call to <EM>f
4</EM>, and if it is not handled induces the computation in progress to halt
(see <A HREF="book-ora017.html#sec-exceptions">??</A>)<BR>
<BR>

<H4> Combining patterns</H4>
<A NAME="@concepts63"></A>
Combining several patterns lets us obtain a new pattern which can
match a value according to one or another of the original patterns.
The syntactic form is as follows:


<H3> Syntax </H3> <HR>


<I>p</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB> <B>|</B> ...<B>|</B> <I>p</I><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB>



<HR>


It constructs a new pattern by combining the patterns <I>p</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB>, ...and <I>p</I><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB>. The only strong constraint is that all naming is
forbidden within these patterns. So each one of them must contain only
constant values or the wildcard pattern. The following example
demonstrates how to verify that a character is a vowel.


<PRE>
<CODE> </CODE><BR># <B>let</B><CODE> </CODE>is_a_vowel<CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>c<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>'a'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'e'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'i'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'o'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'u'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'y'</CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>true</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>false</B><CODE> </CODE>;;<CODE> </CODE><BR><CODE>val is_a_vowel : char -&gt; bool = &lt;fun&gt;</CODE><BR># is_a_vowel<CODE> </CODE><CODE>'i'</CODE><CODE> </CODE>;;<BR><CODE>- : bool = true</CODE><BR># is_a_vowel<CODE> </CODE><CODE>'j'</CODE><CODE> </CODE>;;<BR><CODE>- : bool = false</CODE><BR>

</PRE>
<BR>
<BR>

<H4> Pattern matching of a parameter</H4>
Pattern matching is used in an essential way for defining functions by
cases. To make writing these definitions easier, the syntactic construct
<B>function</B> allows pattern matching of a parameter:


<H3> Syntax </H3> <HR>


<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><B>function</B></TD>
<TD  ALIGN=left NOWRAP><B>|</B></TD>
<TD  ALIGN=left NOWRAP><I>p</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB>  -&gt; expr<SUB><FONT SIZE=2>1</FONT></SUB></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><B>|</B></TD>
<TD  ALIGN=left NOWRAP><I>p</I><SUB><I><FONT SIZE=2>2</FONT></I></SUB>  -&gt; expr<SUB><FONT SIZE=2>2</FONT></SUB></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP>:</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><B>|</B></TD>
<TD  ALIGN=left NOWRAP><I>p</I><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB>  -&gt; expr<SUB><FONT SIZE=2><I>n</I></FONT></SUB></TD>
</TR></TABLE>



<HR>


The vertical bar preceding the first pattern is optional here as well. In
fact, like Mr. Jourdain, each time we define a function, we use
pattern matching<A NAME="text9" HREF="book-ora023.html#note9"><SUP><FONT SIZE=2>7</FONT></SUP></A>. Indeed, the
construction  <EM>function x</EM>  -&gt; expression, is a
definition by pattern matching using a single pattern reduced to one
variable. One can make use of this detail with simple patterns as in:


<PRE><BR># <B>let</B><CODE> </CODE>f<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE><TT>(</TT>x<CODE>,</CODE>y<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE>2</CODE><CODE>*</CODE>x<CODE> </CODE><CODE>+</CODE><CODE> </CODE><CODE>3</CODE><CODE>*</CODE>y<CODE> </CODE><CODE>+</CODE><CODE> </CODE><CODE>4</CODE><CODE> </CODE>;;<BR><CODE>val f : int * int -&gt; int = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
In fact the form
<DIV ALIGN=center>

<B>function</B> <I>p</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB>  -&gt; expr<SUB><FONT SIZE=2>1</FONT></SUB> 
<B>|</B> ...<B>|</B> <I>p</I><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB>  -&gt; expr<SUB><FONT SIZE=2><I>n</I></FONT></SUB>

</DIV>
is equivalent to
<DIV ALIGN=center>

<B>function</B> <I>expr</I>  -&gt; match <EM>expr</EM> <B>with</B>
<I>p</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB>  -&gt; expr<SUB><FONT SIZE=2>1</FONT></SUB> <B>|</B> ...<B>|</B> <I>p</I><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB>  -&gt; expr<SUB><FONT SIZE=2><I>n</I></FONT></SUB> 

</DIV><BR>
Using the equivalence of the declarations mentioned on page
<A HREF="book-ora015.html#dec-fun-equiv">??</A>, we write:


<PRE><BR># <B>let</B><CODE> </CODE>f<CODE> </CODE><TT>(</TT>x<CODE>,</CODE>y<TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>2</CODE><CODE>*</CODE>x<CODE> </CODE><CODE>+</CODE><CODE> </CODE><CODE>3</CODE><CODE>*</CODE>y<CODE> </CODE><CODE>+</CODE><CODE> </CODE><CODE>4</CODE><CODE> </CODE>;;<BR><CODE>val f : int * int -&gt; int = &lt;fun&gt;</CODE><BR>

</PRE>

But this natural way of writing is only possible if the value being matched
belongs to a type having only a single constructor. If such is not the
case, the pattern matching is not exhaustive:


<PRE><BR># <B>let</B><CODE> </CODE>is_zero<CODE> </CODE><CODE>0</CODE><CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>true</B><CODE> </CODE>;;<BR><CODE>Characters 13-21:</CODE><BR><CODE>Warning: this pattern-matching is not exhaustive.</CODE><BR><CODE>Here is an example of a value that is not matched:</CODE><BR><CODE>1</CODE><BR><CODE>val is_zero : int -&gt; bool = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>

<H4> Naming a value being matched</H4>
<A NAME="@concepts64"></A>
<A NAME="@fonctions79"></A>
During pattern matching, it is sometimes useful to name part or all of the
pattern. The following syntactic form introduces the keyword <B>as</B>
which binds a name to a pattern.


<H3> Syntax </H3> <HR>


 <B>(</B> <I>p</I> <B>as</B> <I>name</I> <B>)</B>



<HR>


This is useful when one needs to take apart a value while still maintaining
its integrity. In the following example, the function <TT>min_rat</TT>
gives the smaller rational of a pair of rationals. The latter are each
represented by a numerator and denominator in a pair.<BR>
<BR>


<PRE><BR># <B>let</B><CODE> </CODE>min_rat<CODE> </CODE>pr<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>pr<CODE> </CODE><B>with</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT><TT>(</TT><CODE>_,</CODE><CODE>0</CODE><TT>)</TT><CODE>,</CODE>p2<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>p2<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>p1<CODE>,</CODE><TT>(</TT><CODE>_,</CODE><CODE>0</CODE><TT>)</TT><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>p1<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT><TT>(</TT><TT>(</TT>n1<CODE>,</CODE>d1<TT>)</TT><CODE> </CODE><B>as</B><CODE> </CODE>r1<TT>)</TT><CODE>,</CODE><CODE> </CODE><TT>(</TT><TT>(</TT>n2<CODE>,</CODE>d2<TT>)</TT><CODE> </CODE><B>as</B><CODE> </CODE>r2<TT>)</TT><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE><TT>(</TT>n1<CODE> </CODE><CODE>*</CODE><CODE> </CODE><CODE> </CODE>d2<CODE> </CODE><TT>)</TT><CODE> </CODE><CODE>&lt;</CODE><CODE> </CODE><TT>(</TT>n2<CODE> </CODE><CODE>*</CODE><CODE> </CODE>d1<TT>)</TT><CODE> </CODE><B>then</B><CODE> </CODE>r1<CODE> </CODE><B>else</B><CODE> </CODE>r2;;<BR><CODE>val min_rat : (int * int) * (int * int) -&gt; int * int = &lt;fun&gt;</CODE><BR>

</PRE>

To compare two rationals, it is necessary to take them apart in order to
name their numerators and denominators (<TT>n1</TT>, <TT>n2</TT>,
<TT>d1</TT> and <TT>d2</TT>), but the initial pair (<TT>r1</TT> or
<TT>r2</TT>) must be returned. The <B>as</B> construct allows us to name the
parts of a single value in this way. This lets us avoid having to
reconstruct the rational returned as the result.<BR>
<BR>

<H4> Pattern matching with guards</H4>
<A NAME="@concepts65"></A>
<A NAME="@fonctions80"></A>
Pattern matching with guards corresponds to the evaluation of a conditional
expression immediately after the pattern is matched. If this expression
comes back <EM>true</EM>, then the expression associated with that pattern
is evaluated, otherwise pattern matching continues with the following
pattern. 


<H3> Syntax </H3> <HR>


<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><B>match</B>  <I>expr</I>  <B>with</B></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>   :</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>  <B>|</B>  <I>p</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB>  <B>when</B> <I>cond</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB>   -&gt; <I>expr</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>   :</TD>
</TR></TABLE>



<HR>

<BR>
<BR>
The following example uses two guards to test equality of two rationals.


<PRE><BR># <B>let</B><CODE> </CODE>eq_rat<CODE> </CODE>cr<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>cr<CODE> </CODE><B>with</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT><TT>(</TT><CODE>_,</CODE><CODE>0</CODE><TT>)</TT><CODE>,</CODE><TT>(</TT><CODE>_,</CODE><CODE>0</CODE><TT>)</TT><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><B>true</B><BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT><TT>(</TT><CODE>_,</CODE><CODE>0</CODE><TT>)</TT><CODE>,_</CODE><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><B>false</B><BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT><CODE>_,</CODE><TT>(</TT><CODE>_,</CODE><CODE>0</CODE><TT>)</TT><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><B>false</B><BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT><TT>(</TT>n1<CODE>,</CODE><CODE>1</CODE><TT>)</TT><CODE>,</CODE><CODE> </CODE><TT>(</TT>n2<CODE>,</CODE><CODE>1</CODE><TT>)</TT><TT>)</TT><CODE> </CODE><B>when</B><CODE> </CODE>n1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>n2<CODE> </CODE>-&gt;<CODE> </CODE><B>true</B><BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT><TT>(</TT>n1<CODE>,</CODE>d1<TT>)</TT><CODE>,</CODE><CODE> </CODE><TT>(</TT>n2<CODE>,</CODE>d2<TT>)</TT><TT>)</TT><CODE> </CODE><B>when</B><CODE> </CODE><TT>(</TT><TT>(</TT>n1<CODE> </CODE><CODE>*</CODE><CODE> </CODE>d2<TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>n2<CODE> </CODE><CODE>*</CODE><CODE> </CODE>d1<TT>)</TT><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><B>true</B><BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>false</B>;;<BR><CODE>val eq_rat : (int * int) * (int * int) -&gt; bool = &lt;fun&gt;</CODE><BR>

</PRE>

If the guard fails when the fourth pattern is matched, matching continues with
the fifth pattern.<BR>
<BR>


<H3> Note </H3> <HR>

The verification carried out by Objective CAML as to whether the pattern
matching is exhaustive assumes that the conditional expression in the guard
may be false. Consequently, it does not count this pattern since it is not
possible to know, before execution, whether the guard will be satisfied or
not.


<HR>


It won't be possible to detect that the pattern matching in the following
example is exhaustive.


<PRE><BR># <CODE> </CODE><B>let</B><CODE> </CODE>f<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE>x<CODE> </CODE><B>when</B><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>x<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>true</B>;;<CODE> </CODE><BR><CODE>Characters 10-40:</CODE><BR><CODE>Warning: this pattern-matching is not exhaustive.</CODE><BR><CODE>Here is an example of a value that is not matched:</CODE><BR><CODE>_</CODE><BR><CODE>val f : 'a -&gt; bool = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>

<H4> Pattern matching on character intervals</H4>
<A NAME="@concepts66"></A>In the context of pattern matching on characters,
it is tedious to construct the combination of all the patterns
corresponding to a character interval. Indeed, if one wishes to test a
character or even a letter, one would need to write 26 patterns at a
minimum and combine them. For characters, Objective CAML permits writing
patterns of the form:


<H3> Syntax </H3> <HR>


 <TT>'c</TT><SUB><TT><FONT SIZE=2>1</FONT></TT></SUB><TT>'</TT> .. <TT>'c</TT><SUB><TT><FONT SIZE=2><I>n</I></FONT></TT></SUB><TT>'</TT>



<HR>


It is equivalent to the combination:
<EM>'c</EM><SUB><EM><FONT SIZE=2>1</FONT></EM></SUB><EM>' | 'c</EM><SUB><EM><FONT SIZE=2>2</FONT></EM></SUB><EM>' | ...| 'c</EM><SUB><EM><FONT SIZE=2><I>n</I></FONT></EM></SUB><EM>'</EM>.<BR>
<BR>
For example the pattern <EM>'0' .. '9'</EM> corresponds to the pattern
<EM>'0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'</EM>. The
first form is nicer to read and quicker to write.


<H3> Warning </H3> <HR>

This feature is among the extensions to the language and may change in
future versions.


<HR>


Using combined patterns and intervals, we define a function categorizing
characters according to several criteria.


<PRE><BR># <B>let</B><CODE> </CODE>char_discriminate<CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>c<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>'a'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'e'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'i'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'o'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'u'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'y'</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'A'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'E'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'I'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'O'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'U'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'Y'</CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"Vowel"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'a'</CODE><CODE>..</CODE><CODE>'z'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'A'</CODE><CODE>..</CODE><CODE>'Z'</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"Consonant"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'0'</CODE><CODE>..</CODE><CODE>'9'</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"Digit"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"Other"</CODE><CODE> </CODE>;;<BR><CODE>val char_discriminate : char -&gt; string = &lt;fun&gt;</CODE><BR>

</PRE>

It should be noted that the order of the groups of patterns has some
significance. Indeed, the second set of patterns includes the first, but
it is not examined until after the check on the first.<BR>
<BR>

<H4> Pattern matching on lists</H4>
<A NAME="subsub-filtrage-liste"></A>
<A NAME="@concepts67"></A>
As we have seen, a list can be:
<UL>
<LI>
 either empty (the list is of the form <B>[]</B>),

<LI> or composed of a first element (its head) and a sublist (its tail). The
list is then of the form
<EM>h</EM><CODE>::</CODE><EM>t</EM>.
</UL>
These two possible ways of writing a list can be used as patterns and allow
pattern matching on a list.


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>size<CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>x<CODE> </CODE><B>with</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE><CODE>0</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_::</CODE>tail_x<CODE> </CODE>-&gt;<CODE> </CODE><CODE>1</CODE><CODE> </CODE><CODE>+</CODE><CODE> </CODE><TT>(</TT>size<CODE> </CODE>tail_x<TT>)</TT><CODE> </CODE>;;<BR><CODE>val size : 'a list -&gt; int = &lt;fun&gt;</CODE><BR># size<CODE> </CODE>[];;<BR><CODE>- : int = 0</CODE><BR># size<CODE> </CODE><CODE>[</CODE><CODE>7</CODE>;<CODE>9</CODE>;<CODE>2</CODE>;<CODE>6</CODE><CODE>]</CODE>;;<BR><CODE>- : int = 4</CODE><BR>

</PRE>
<BR>
<BR>
So we can redo the examples described previously (see page
<A HREF="book-ora015.html#sub-ex-liste">??</A>) using pattern matching,
such as iteration over lists for example.


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>fold_left<CODE> </CODE>f<CODE> </CODE>a<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE>a<BR><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>head::tail<CODE> </CODE>-&gt;<CODE> </CODE>fold_left<CODE> </CODE>f<CODE> </CODE><TT>(</TT>f<CODE> </CODE>a<CODE> </CODE>head<TT>)</TT><CODE> </CODE>tail<CODE> </CODE>;;<BR><CODE>val fold_left : ('a -&gt; 'b -&gt; 'a) -&gt; 'a -&gt; 'b list -&gt; 'a = &lt;fun&gt;</CODE><BR># fold_left<CODE> </CODE><TT>(</TT><CODE>+</CODE><TT>)</TT><CODE> </CODE><CODE>0</CODE><CODE> </CODE><CODE>[</CODE><CODE>8</CODE>;<CODE>4</CODE>;<CODE>1</CODE><CODE>0</CODE><CODE>]</CODE>;;<BR><CODE>- : int = 22</CODE><BR>

</PRE>
<BR>
<BR>

<H4> Value declaration through pattern matching</H4>
<A NAME="@concepts68"></A>
Value declaration in fact uses pattern matching. The declaration
<B>let</B><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>1</CODE><CODE>8</CODE> matches the value <CODE>1</CODE><CODE>8</CODE> with the pattern
x. Any pattern is allowed as the left-hand side of a
declaration; the variables in the pattern are bound to the values which
they match.


<PRE><BR># <B>let</B><CODE> </CODE><TT>(</TT>a<CODE>,</CODE>b<CODE>,</CODE>c<TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT><CODE>1</CODE><CODE>,</CODE><CODE> </CODE><B>true</B><CODE>,</CODE><CODE> </CODE><CODE>'A'</CODE><TT>)</TT>;;<BR><CODE>val a : int = 1</CODE><BR><CODE>val b : bool = true</CODE><BR><CODE>val c : char = 'A'</CODE><BR># <B>let</B><CODE> </CODE><TT>(</TT>d<CODE>,</CODE>c<TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>8</CODE><CODE>,</CODE><CODE> </CODE><CODE>3</CODE><CODE> </CODE><B>in</B><CODE> </CODE>d<CODE> </CODE><CODE>+</CODE><CODE> </CODE>c;;<BR><CODE>- : int = 11</CODE><BR>

</PRE>
 
The scope of pattern variables is the usual static scope for local 
declarations. Here, <TT>c</TT> remains bound to the
value <CODE>'A'</CODE>. 


<PRE><BR># a<CODE> </CODE><CODE>+</CODE><CODE> </CODE><TT>(</TT>int_of_char<CODE> </CODE>c<TT>)</TT>;;<BR><CODE>- : int = 66</CODE><BR>

</PRE>
<BR>
<BR>
As with any kind of pattern matching, value declaration may not be exhaustive.


<PRE><BR># <B>let</B><CODE> </CODE><CODE>[</CODE>x;y;z<CODE>]</CODE><CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[</CODE><CODE>1</CODE>;<CODE>2</CODE>;<CODE>3</CODE><CODE>]</CODE>;;<BR><CODE>Characters 5-12:</CODE><BR><CODE>Warning: this pattern-matching is not exhaustive.</CODE><BR><CODE>Here is an example of a value that is not matched:</CODE><BR><CODE>[]</CODE><BR><CODE>val x : int = 1</CODE><BR><CODE>val y : int = 2</CODE><BR><CODE>val z : int = 3</CODE><BR># <B>let</B><CODE> </CODE><CODE>[</CODE>x;y;z<CODE>]</CODE><CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[</CODE><CODE>1</CODE>;<CODE>2</CODE>;<CODE>3</CODE>;<CODE>4</CODE><CODE>]</CODE>;;<BR><CODE>Characters 4-11:</CODE><BR><CODE>Warning: this pattern-matching is not exhaustive.</CODE><BR><CODE>Here is an example of a value that is not matched:</CODE><BR><CODE>[]</CODE><BR><CODE>Uncaught exception: Match_failure("", 4, 11)</CODE><BR>

</PRE>
<BR>
<BR>
Any pattern is allowed, including constructors, wildcards and combined
patterns.


<PRE><BR># <B>let</B><CODE> </CODE>head<CODE> </CODE>::<CODE> </CODE><CODE>2</CODE><CODE> </CODE>::<CODE> </CODE><CODE>_</CODE><CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE> </CODE><CODE>[</CODE><CODE>1</CODE>;<CODE> </CODE><CODE>2</CODE>;<CODE> </CODE><CODE>3</CODE><CODE>]</CODE><CODE> </CODE>;;<BR><CODE>Characters 5-19:</CODE><BR><CODE>Warning: this pattern-matching is not exhaustive.</CODE><BR><CODE>Here is an example of a value that is not matched:</CODE><BR><CODE>[]</CODE><BR><CODE>val head : int = 1</CODE><BR># <B>let</B><CODE> </CODE><CODE>_</CODE><CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>3</CODE><CODE>.</CODE><CODE> </CODE><CODE>+.</CODE><CODE> </CODE><CODE>0</CODE><CODE>.</CODE><CODE>1</CODE><CODE>4</CODE><CODE> </CODE><B>in</B><CODE> </CODE><CODE>"PI"</CODE><CODE> </CODE>;;<BR><CODE>- : string = "PI"</CODE><BR>

</PRE>
<BR>
<BR>
This last example is of little use in the functional world insofar as
the computed value <CODE>3</CODE><CODE>.</CODE><CODE>1</CODE><CODE>4</CODE> is not named and so is lost. <BR>
<BR>
<A NAME="toc15"></A>
<H3> Type declaration</H3>
<A NAME="subsec-decltypes"></A>
<A NAME="@concepts69"></A><A NAME="@concepts70"></A>
<A NAME="@concepts71"></A>
<A NAME="@concepts72"></A>
<A NAME="@fonctions81"></A>
Type declarations are another possible ingredient in an Objective CAML phrase.
They support the definition of new types corresponding to the original data
structures used in a program. There are two major families of types:
product types for tuples or records; and sum types for
unions.<BR>
<BR>
Type declarations use the keyword <B>type</B>.


<H3> Syntax </H3> <HR>


<B>type</B> <I>name</I> <B>=</B> <I>typedef</I> <B>;;</B>



<HR>


In contrast with variable declarations, type declarations are recursive by
default. That is, type declarations, when combined, support the declaration
of mutually recursive types.
<A NAME="@concepts73"></A>
<A NAME="@fonctions82"></A>


<H3> Syntax </H3> <HR>


<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><B>type</B></TD>
<TD  ALIGN=left NOWRAP><I>name</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB></TD>
<TD  ALIGN=left NOWRAP><B>=</B></TD>
<TD  ALIGN=left NOWRAP><I>typedef</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><B>and</B></TD>
<TD  ALIGN=left NOWRAP><I>name</I><SUB><I><FONT SIZE=2>2</FONT></I></SUB></TD>
<TD  ALIGN=left NOWRAP><B>=</B></TD>
<TD  ALIGN=left NOWRAP><I>typedef</I><SUB><I><FONT SIZE=2>2</FONT></I></SUB></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP>:</TD>
<TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><B>and</B></TD>
<TD  ALIGN=left NOWRAP><I>name</I><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB></TD>
<TD  ALIGN=left NOWRAP><B>=</B></TD>
<TD  ALIGN=left NOWRAP><I>typedef</I><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB> <B>;;</B></TD>
</TR></TABLE>



<HR>


<A NAME="@concepts74"></A>
Type declarations can be parameterized by type variables. A type variable
name always begins with an apostrophe 
(the <B>'</B> character): 


<H3> Syntax </H3> <HR>


<B>type</B> <B>'</B><I>a</I> <I>name</I> <B>=</B> <I>typedef</I> <B>;;</B>



<HR>


When there are several of them, the type parameters are declared as a tuple in
front of the name of the type:


<H3> Syntax </H3> <HR>


<B>type</B>
<B>(</B><B>'</B><I>a</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB> ...<B>'</B><I>a</I><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB><B>)</B>
<I>name</I> <B>=</B> <I>typedef</I> <B>;;</B>



<HR>


Only the type parameters defined on the left-hand side of the declaration
may appear on the right-hand side.


<H3> Note </H3> <HR>

Objective CAML's type printer renames the type parameters encountered; the
first is called <I>'a</I>, the second <I>'b</I>
and so forth.


<HR>

<BR>
<BR>
One can always define a new type from one or more existing types.


<H3> Syntax </H3> <HR>


<B>type</B> <I>name</I> <B>=</B> <I>type expression</I>



<HR>


This is useful for constraining a type which one finds too general.


<PRE><BR># <B>type</B><CODE> </CODE><I>'param</I><CODE> </CODE>paired_with_integer<CODE> </CODE><CODE>=</CODE><CODE> </CODE>int<CODE> </CODE><CODE>*</CODE><CODE> </CODE><I>'param</I><CODE> </CODE>;;<BR><CODE>type 'a paired_with_integer = int * 'a</CODE><BR># <B>type</B><CODE> </CODE>specific_pair<CODE> </CODE><CODE>=</CODE><CODE> </CODE>float<CODE> </CODE>paired_with_integer<CODE> </CODE>;;<BR><CODE>type specific_pair = float paired_with_integer</CODE><BR>

</PRE>
<BR>
<BR>
Nevertheless without type constraints, inference will produce the most
general type.


<PRE><BR># <B>let</B><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT><CODE>3</CODE><CODE>,</CODE><CODE> </CODE><CODE>3</CODE><CODE>.</CODE><CODE>1</CODE><CODE>4</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>val x : int * float = 3, 3.14</CODE><BR>

</PRE>
<BR>
<BR>
But one can use a type constraint to see the desired name appear:


<PRE><BR># <B>let</B><CODE> </CODE><TT>(</TT>x<CODE>:</CODE>specific_pair<TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT><CODE>3</CODE><CODE>,</CODE><CODE> </CODE><CODE>3</CODE><CODE>.</CODE><CODE>1</CODE><CODE>4</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>val x : specific_pair = 3, 3.14</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc16"></A>
<H3> Records</H3>
<A NAME="subsec-enregistements"></A>
<A NAME="@concepts75"></A><A NAME="@concepts76"></A>Records are tuples, each of whose fields is named in the same way as the
Pascal <EM>record</EM> or the C <EM>struct</EM>. A record always
corresponds to the declaration of a new type. A record type is defined by
the declaration of its name and the names and types of each of its fields.<BR>
<BR>


<H3> Syntax </H3> <HR>


<B>type</B> <I>name</I> <B>=</B>
<B>{</B> <I>name</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB> <B>:</B> <I>t</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB><B>;</B>
...<B>;</B> <I>name</I><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB> <B>:</B> <I>t</I><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB>
<B>}</B> <B>;;</B>



<HR>


We can define a type representing complex numbers by:


<PRE><BR># <B>type</B><CODE> </CODE>complex<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>re<CODE>:</CODE>float;<CODE> </CODE>im<CODE>:</CODE>float<CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>type complex = { re: float; im: float }</CODE><BR>

</PRE>
<BR>
<BR>
The creation of a value of record type is done by giving a value to each of
its fields (in arbitrary order).


<H3> Syntax </H3> <HR>


<B>{</B> <I>name</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB><SUB><SUB><I><FONT SIZE=2>1</FONT></I></SUB></SUB> <B>=</B> <I>expr</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB><SUB><SUB><I><FONT SIZE=2>1</FONT></I></SUB></SUB><B>;</B>
...<B>;</B> <I>name</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB><SUB><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB></SUB> <B>=</B> <I>expr</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB><SUB><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB></SUB>
<B>}</B> <B>;;</B>



<HR>


For example, we create a complex number with real part
<EM>2.</EM> and imaginary part <EM>3.</EM>:


<PRE><BR># <B>let</B><CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{re<CODE>=</CODE><CODE>2</CODE><CODE>.</CODE>;im<CODE>=</CODE><CODE>3</CODE><CODE>.}</CODE><CODE> </CODE>;;<BR><CODE>val c : complex = {re=2; im=3}</CODE><BR># c<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{im<CODE>=</CODE><CODE>3</CODE><CODE>.</CODE>;re<CODE>=</CODE><CODE>2</CODE><CODE>.}</CODE><CODE> </CODE>;;<BR><CODE>- : bool = true</CODE><BR>

</PRE>
<BR>
<BR>
In the case where some fields are missing, the following error is produced:


<PRE><BR># <B>let</B><CODE> </CODE>d<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>im<CODE>=</CODE><CODE>4</CODE><CODE>.</CODE><CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>Characters 9-18:</CODE><BR><CODE>Some labels are undefined</CODE><BR>

</PRE>
<BR>
<BR>
A field can be accessed in two ways: by the dot notation or by pattern
matching on certain fields.<BR>
<BR>
The dot notation syntax is as usual:


<H3> Syntax </H3> <HR>


<I>expr</I>.<I>name</I>



<HR>


The expression <I>expr</I> must be of a record type containing a field
<I>name</I>.<BR>
<BR>
Pattern matching a record lets one retrieve the value bound to several
fields. A pattern to match a record has the following syntax:


<H3> Syntax </H3> <HR>


<B>{</B> <I>name</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB> <B>=</B> <I>p</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB> <B>;</B>
...<B>;</B> <I>name</I><SUB><I><FONT SIZE=2><I>j</I></FONT></I></SUB> <B>=</B> <I>p</I><SUB><I><FONT SIZE=2><I>j</I></FONT></I></SUB> <B>}</B>



<HR>


The patterns are to the right of the <B>=</B> sign (<I>p</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB>, ...,
<I>p</I><SUB><I><FONT SIZE=2><I>j</I></FONT></I></SUB>). It is not necessary to make all the fields of a record
appear in such a pattern.<BR>
<BR>
The function <TT>add_complex</TT> accesses fields through the dot
notation, while the function <TT>mult_complex</TT> accesses them through
pattern matching.


<PRE><BR># <B>let</B><CODE> </CODE>add_complex<CODE> </CODE>c1<CODE> </CODE>c2<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE> </CODE>{re<CODE>=</CODE>c1<CODE>.</CODE>re<CODE>+.</CODE>c2<CODE>.</CODE>re;<CODE> </CODE>im<CODE>=</CODE>c1<CODE>.</CODE>im<CODE>+.</CODE>c2<CODE>.</CODE>im};;<BR><CODE>val add_complex : complex -&gt; complex -&gt; complex = &lt;fun&gt;</CODE><BR># add_complex<CODE> </CODE>c<CODE> </CODE>c<CODE> </CODE>;;<BR><CODE>- : complex = {re=4; im=6}</CODE><BR># <B>let</B><CODE> </CODE>mult_complex<CODE> </CODE>c1<CODE> </CODE>c2<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE><TT>(</TT>c1<CODE>,</CODE>c2<TT>)</TT><CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT>{re<CODE>=</CODE>x1;im<CODE>=</CODE>y1<CODE>},{</CODE>re<CODE>=</CODE>x2;im<CODE>=</CODE>y2}<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE>{re<CODE>=</CODE>x1<CODE>*.</CODE>x2<CODE>-.</CODE>y1<CODE>*.</CODE>y2;im<CODE>=</CODE>x1<CODE>*.</CODE>y2<CODE>+.</CODE>x2<CODE>*.</CODE>y1}<CODE> </CODE>;;<BR><CODE>val mult_complex : complex -&gt; complex -&gt; complex = &lt;fun&gt;</CODE><BR># mult_complex<CODE> </CODE>c<CODE> </CODE>c<CODE> </CODE>;;<BR><CODE>- : complex = {re=-5; im=12}</CODE><BR>

</PRE>
<BR>
<BR>
The advantages of records, as opposed to tuples, are at least twofold:
<UL>
<LI>
 descriptive and distinguishing information thanks to the field names: in
particular this allows pattern matching to be simplified;

<LI> access in an identical way, by name, to any field of the record
whatsoever: the order of the fields no longer has significance, only their
names count.
</UL> The following example shows the ease of accessing the fields of
records as opposed to tuples:


<PRE><BR># <B>let</B><CODE> </CODE>a<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT><CODE>1</CODE><CODE>,</CODE><CODE>2</CODE><CODE>,</CODE><CODE>3</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>val a : int * int * int = 1, 2, 3</CODE><BR># <B>let</B><CODE> </CODE>f<CODE> </CODE>tr<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>tr<CODE> </CODE><B>with</B><CODE> </CODE><CODE> </CODE>x<CODE>,_,_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>x<CODE> </CODE>;;<BR><CODE>val f : 'a * 'b * 'c -&gt; 'a = &lt;fun&gt;</CODE><BR># f<CODE> </CODE>a<CODE> </CODE>;;<BR><CODE>- : int = 1</CODE><BR># <B>type</B><CODE> </CODE>triplet<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{x1<CODE>:</CODE>int;<CODE> </CODE>x2<CODE>:</CODE>int;<CODE> </CODE>x3<CODE>:</CODE>int}<CODE> </CODE>;;<BR><CODE>type triplet = { x1: int; x2: int; x3: int }</CODE><BR># <B>let</B><CODE> </CODE>b<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{x1<CODE>=</CODE><CODE>1</CODE>;<CODE> </CODE>x2<CODE>=</CODE><CODE>2</CODE>;<CODE> </CODE>x3<CODE>=</CODE><CODE>3</CODE>}<CODE> </CODE>;;<BR><CODE>val b : triplet = {x1=1; x2=2; x3=3}</CODE><BR># <B>let</B><CODE> </CODE>g<CODE> </CODE>tr<CODE> </CODE><CODE>=</CODE><CODE> </CODE>tr<CODE>.</CODE>x1<CODE> </CODE>;;<BR><CODE>val g : triplet -&gt; int = &lt;fun&gt;</CODE><BR># g<CODE> </CODE>b<CODE> </CODE>;;<BR><CODE>- : int = 1</CODE><BR>

</PRE>
<BR>
<BR>
For pattern matching, it is not necessary to indicate all the fields of the
record being matched. The inferred type is then that of the last field.


<PRE><BR># <B>let</B><CODE> </CODE>h<CODE> </CODE>tr<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>tr<CODE> </CODE><B>with</B><CODE> </CODE><CODE> </CODE>{x1<CODE>=</CODE>x}<CODE> </CODE>-&gt;<CODE> </CODE>x;;<BR><CODE>val h : triplet -&gt; int = &lt;fun&gt;</CODE><BR># h<CODE> </CODE>b;;<BR><CODE>- : int = 1</CODE><BR>

</PRE>
<BR>
<BR>
There is a construction which lets one create a record identical to
another except for some fields. It is often useful for records containing
many fields.
<A NAME="@fonctions83"></A>


<H3> Syntax </H3> <HR>


{ <I>name</I> <B>with</B> <I>name</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB><B>=</B> <I>expr</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB> 
<B>;</B> ...<B>;</B> <I>name</I><SUB><I><FONT SIZE=2><I>j</I></FONT></I></SUB><B>=</B><I>expr</I><SUB><I><FONT SIZE=2><I>j</I></FONT></I></SUB>}



<HR>

<BR>
<BR>


<PRE><BR># <B>let</B><CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{b<CODE> </CODE><B>with</B><CODE> </CODE>x1<CODE>=</CODE><CODE>0</CODE>}<CODE> </CODE>;;<BR><CODE>val c : triplet = {x1=0; x2=2; x3=3}</CODE><BR>

</PRE>

A new copy of the value of <TT>b</TT> is created where only the field
<TT>x1</TT> has a new value.


<H3> Warning </H3> <HR>

This feature is among the extensions to the language and may change in
future versions.


<HR>

<BR>
<BR>
<A NAME="toc17"></A>
<H3> Sum types</H3>
<A NAME="subsec-typ-somme"></A>
<A NAME="@concepts77"></A>
<A NAME="@concepts78"></A>
<A NAME="@concepts79"></A>
<A NAME="@concepts80"></A>
<A NAME="@fonctions84"></A>
In contrast with tuples or records, which correspond to a Cartesian
product, the declaration of a sum type corresponds to a union of sets.
Different types (for example integers or character strings) are gathered
into a single type. The various members of the sum are distinguished by
constructors, which support on the one hand, as their name
indicates, <EM>construction</EM> of values of this type and on the other hand,
thanks to pattern matching, <EM>access</EM> to the components of these values.
To apply a constructor to an argument is to indicate that the value
returned belongs to this new type.<BR>
<BR>
A sum type is declared by giving the names of its constructors and the
types of their eventual arguments.


<H3> Syntax </H3> <HR>

 <TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><B>type</B></TD>
<TD  ALIGN=left NOWRAP><I>name</I> <B>=</B> ...</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><B>|</B> <I>Name</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB> ...</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><B>|</B> <I>Name</I><SUB><I><FONT SIZE=2><I>j</I></FONT></I></SUB> <B>of</B> <I>t</I><SUB><I><FONT SIZE=2><I>j</I></FONT></I></SUB> ...</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><B>|</B> <I>Name</I><SUB><I><FONT SIZE=2><I>k</I></FONT></I></SUB> <B>of</B> <I>t</I><SUB><I><FONT SIZE=2><I>k</I></FONT></I></SUB><I> * ...* t</I><SUB><I><FONT SIZE=2><I>l</I></FONT></I></SUB>
 ...<B>;;</B></TD>
</TR></TABLE>
 


<HR>

<BR>
<BR>
A constructor name is a particular identifier:


<H3> Warning </H3> <HR>


The names of constructors always begin with a capital letter.



<HR>

<BR>
<BR>

<H4> Constant constructors</H4>
<A NAME="@concepts81"></A>
A constructor which doesn't expect an argument is called a constant
constructor. Constant constructors can subsequently be used directly as a
value in the language, as a constant.


<PRE><BR># <B>type</B><CODE> </CODE>coin<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Heads<CODE> </CODE><CODE>|</CODE><CODE> </CODE>Tails;;<BR><CODE>type coin = | Heads | Tails</CODE><BR># Tails;;<BR><CODE>- : coin = Tails</CODE><BR>

</PRE>

The type <I>bool</I> can be defined in this way.<BR>
<BR>

<H4> Constructors with arguments</H4>
<A NAME="@concepts82"></A>
Constructors can have arguments. The keyword <B>of</B>
indicates the type of the constructor's arguments. This supports the
gathering into a single type of objects of different types, each one being
introduced with a particular constructor.<BR>
<BR>
Here is a classic example of defining a datatype to represent the cards in
a game, here Tarot<A NAME="text10" HREF="book-ora023.html#note10"><SUP><FONT SIZE=2>8</FONT></SUP></A>. The types
<I>suit</I> and <I>card</I> are defined in the following way:


<PRE><BR># <B>type</B><CODE> </CODE>suit<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Spades<CODE> </CODE><CODE>|</CODE><CODE> </CODE>Hearts<CODE> </CODE><CODE>|</CODE><CODE> </CODE>Diamonds<CODE> </CODE><CODE>|</CODE><CODE> </CODE>Clubs<CODE> </CODE>;;<BR># <B>type</B><CODE> </CODE>card<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>King<CODE> </CODE><B>of</B><CODE> </CODE>suit<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Queen<CODE> </CODE><B>of</B><CODE> </CODE>suit<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Knight<CODE> </CODE><B>of</B><CODE> </CODE>suit<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Knave<CODE> </CODE><B>of</B><CODE> </CODE>suit<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Minor_card<CODE> </CODE><B>of</B><CODE> </CODE>suit<CODE> </CODE><CODE>*</CODE><CODE> </CODE>int<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Trump<CODE> </CODE><B>of</B><CODE> </CODE>int<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Joker<CODE> </CODE>;;<BR>

</PRE>
<BR>
<BR>
The creation of a value of type <I>card</I> is carried out through the
application of a constructor to a value of the appropriate type.


<PRE><BR># King<CODE> </CODE>Spades<CODE> </CODE>;;<BR><CODE>- : card = King Spades</CODE><BR># Minor_card<TT>(</TT>Hearts<CODE>,</CODE><CODE> </CODE><CODE>1</CODE><CODE>0</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>- : card = Minor_card (Hearts, 10)</CODE><BR># Trump<CODE> </CODE><CODE>2</CODE><CODE>1</CODE><CODE> </CODE>;;<BR><CODE>- : card = Trump 21</CODE><BR>

</PRE>
<BR>
<BR>
And here, for example, is the function <TT>all_cards</TT> which
constructs a list of all the cards of a suit passed as a parameter.


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>interval<CODE> </CODE>a<CODE> </CODE>b<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>a<CODE> </CODE><CODE>=</CODE><CODE> </CODE>b<CODE> </CODE><B>then</B><CODE> </CODE><CODE>[</CODE>b<CODE>]</CODE><CODE> </CODE><B>else</B><CODE> </CODE>a::<TT>(</TT>interval<CODE> </CODE><TT>(</TT>a<CODE>+</CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE>b<TT>)</TT><CODE> </CODE>;;<BR><CODE>val interval : int -&gt; int -&gt; int list = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>all_cards<CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>face_cards<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[</CODE><CODE> </CODE>Knave<CODE> </CODE>s;<CODE> </CODE>Knight<CODE> </CODE>s;<CODE> </CODE>Queen<CODE> </CODE>s;<CODE> </CODE>King<CODE> </CODE>s<CODE> </CODE><CODE>]</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>and</B><CODE> </CODE>other_cards<CODE> </CODE><CODE> </CODE><CODE>=</CODE><CODE> </CODE>List.map<CODE> </CODE><TT>(</TT><B>function</B><CODE> </CODE>n<CODE> </CODE>-&gt;<CODE> </CODE>Minor_card<TT>(</TT>s<CODE>,</CODE>n<TT>)</TT><TT>)</TT><CODE> </CODE><TT>(</TT>interval<CODE> </CODE><CODE>1</CODE><CODE> </CODE><CODE>1</CODE><CODE>0</CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>face_cards<CODE> </CODE><CODE>@</CODE><CODE> </CODE>other_cards<CODE> </CODE>;;<BR><CODE>val all_cards : suit -&gt; card list = &lt;fun&gt;</CODE><BR># all_cards<CODE> </CODE>Hearts<CODE> </CODE>;;<BR><CODE>- : card list =</CODE><BR><CODE>[Knave Hearts; Knight Hearts; Queen Hearts; King Hearts;</CODE><BR><CODE> Minor_card (Hearts, 1); Minor_card (Hearts, 2); Minor_card (Hearts, 3);</CODE><BR><CODE> Minor_card (Hearts, ...); ...]</CODE><BR>

</PRE>
<BR>
<BR>
To handle values of sum types, we use pattern matching. The following
example constructs conversion functions from values of type <I>suit</I>
and of type <I>card</I> to character strings (type <I>string</I>):


<PRE><BR># <B>let</B><CODE> </CODE>string_of_suit<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Spades<CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"spades"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE>Diamonds<CODE> </CODE>-&gt;<CODE> </CODE><CODE>"diamonds"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE>Hearts<CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"hearts"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE>Clubs<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"clubs"</CODE><CODE> </CODE><CODE> </CODE>;;<BR><CODE>val string_of_suit : suit -&gt; string = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>string_of_card<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>King<CODE> </CODE>c<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"king of "</CODE><CODE> </CODE><CODE>^</CODE><CODE> </CODE><TT>(</TT>string_of_suit<CODE> </CODE>c<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE>Queen<CODE> </CODE>c<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"queen of "</CODE><CODE> </CODE><CODE>^</CODE><CODE> </CODE><TT>(</TT>string_of_suit<CODE> </CODE>c<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE>Knave<CODE> </CODE>c<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"knave of "</CODE><CODE> </CODE><CODE>^</CODE><CODE> </CODE><TT>(</TT>string_of_suit<CODE> </CODE>c<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE>Knight<CODE> </CODE>c<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"knight of "</CODE><CODE> </CODE><CODE>^</CODE><CODE> </CODE><TT>(</TT>string_of_suit<CODE> </CODE>c<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE>Minor_card<CODE> </CODE><TT>(</TT>c<CODE>,</CODE><CODE> </CODE>n<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT>string_of_int<CODE> </CODE>n<TT>)</TT><CODE> </CODE><CODE>^</CODE><CODE> </CODE><CODE>" of "</CODE><CODE>^</CODE><TT>(</TT>string_of_suit<CODE> </CODE>c<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE>Trump<CODE> </CODE>n<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT>string_of_int<CODE> </CODE>n<TT>)</TT><CODE> </CODE><CODE>^</CODE><CODE> </CODE><CODE>" of trumps"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE>Joker<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"joker"</CODE><CODE> </CODE>;;<BR><CODE>val string_of_card : card -&gt; string = &lt;fun&gt;</CODE><BR>

</PRE>

Lining up the patterns makes these functions easy to read.<BR>
<BR>
The constructor <TT>Minor_card</TT> is treated as a constructor with
<EM>two</EM> arguments. Pattern matching on such a value requires naming
its two components.


<PRE><BR># <B>let</B><CODE> </CODE>is_minor_card<CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>c<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Minor_card<CODE> </CODE>v<CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><B>true</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>false</B>;;<BR><CODE>Characters 41-53:</CODE><BR><CODE>The constructor Minor_card expects 2 argument(s),</CODE><BR><CODE>but is here applied to 1 argument(s)</CODE><BR>

</PRE>
<BR>
<BR>
To avoid having to name each component of a constructor, one declares it to
have a single argument by parenthesizing the corresponding tuple type.
The two constructors which follow are pattern-matched differently.


<PRE><BR># <B>type</B><CODE> </CODE>t<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>C<CODE> </CODE><B>of</B><CODE> </CODE>int<CODE> </CODE><CODE>*</CODE><CODE> </CODE>bool<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE>D<CODE> </CODE><B>of</B><CODE> </CODE><TT>(</TT>int<CODE> </CODE><CODE>*</CODE><CODE> </CODE>bool<TT>)</TT><CODE> </CODE>;;<BR># <B>let</B><CODE> </CODE>access<CODE> </CODE>v<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>v<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>C<CODE> </CODE><TT>(</TT>i<CODE>,</CODE><CODE> </CODE>b<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE>i<CODE>,</CODE>b<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE>D<CODE> </CODE>x<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE>x;;<BR><CODE>val access : t -&gt; int * bool = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc18"></A>
<H3> Recursive types</H3><A NAME="sec-type-rec"></A>
<A NAME="@concepts83"></A>
Recursive type definitions are indispensable in any algorithmic language
for describing the usual data structures (lists, heaps, trees, graphs,
etc.). To this end, in Objective CAML type definition is recursive by default,
in contrast with value declaration (<B>let</B>).<BR>
<BR>
Objective CAML's predefined type of lists only takes a single parameter. One may
wish to store values of belonging to two different types in a list
structure, for example, integers (<I>int</I>) or characters
(<I>char</I>). In this case, one defines:


<PRE><BR># <B>type</B><CODE> </CODE>int_or_char_list<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Nil<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE>Int_cons<CODE> </CODE><B>of</B><CODE> </CODE>int<CODE> </CODE><CODE>*</CODE><CODE> </CODE>int_or_char_list<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE>Char_cons<CODE> </CODE><B>of</B><CODE> </CODE>char<CODE> </CODE><CODE>*</CODE><CODE> </CODE>int_or_char_list<CODE> </CODE>;;<BR>

</PRE>



<PRE><BR># <B>let</B><CODE> </CODE>l1<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE> </CODE>Char_cons<CODE> </CODE><TT>(</TT><CODE> </CODE><CODE>'='</CODE><CODE>,</CODE><CODE> </CODE>Int_cons<TT>(</TT><CODE>5</CODE><CODE>,</CODE><CODE> </CODE>Nil<TT>)</TT><CODE> </CODE><TT>)</TT><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Int_cons<CODE> </CODE><TT>(</TT><CODE> </CODE><CODE>2</CODE><CODE>,</CODE><CODE> </CODE>Char_cons<CODE> </CODE><TT>(</TT><CODE> </CODE><CODE>'+'</CODE><CODE>,</CODE><CODE> </CODE>Int_cons<TT>(</TT><CODE>3</CODE><CODE>,</CODE><CODE> </CODE>l1<TT>)</TT><CODE> </CODE><TT>)</TT><CODE> </CODE><TT>)</TT><CODE> </CODE><CODE> </CODE>;;<BR><CODE>- : int_or_char_list =</CODE><BR><CODE>Int_cons (2, Char_cons ('+', Int_cons (3, Char_cons ('=', Int_cons (...)))))</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc19"></A>
<H3> Parametrized types</H3>
<A NAME="@concepts84"></A>
A user can equally well declare types with parameters. This lets us
generalize the example of lists containing values of two different
types.


<PRE><BR># <B>type</B><CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><CODE> </CODE><I>'b</I><TT>)</TT><CODE> </CODE>list2<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Nil<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE>Acons<CODE> </CODE><B>of</B><CODE> </CODE><I>'a</I><CODE> </CODE><CODE>*</CODE><CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><CODE> </CODE><I>'b</I><TT>)</TT><CODE> </CODE>list2<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE>Bcons<CODE> </CODE><B>of</B><CODE> </CODE><I>'b</I><CODE> </CODE><CODE>*</CODE><CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><CODE> </CODE><I>'b</I><TT>)</TT><CODE> </CODE>list2<CODE> </CODE>;;<BR>

</PRE>



<PRE><BR># Acons<TT>(</TT><CODE>2</CODE><CODE>,</CODE><CODE> </CODE>Bcons<TT>(</TT><CODE>'+'</CODE><CODE>,</CODE><CODE> </CODE>Acons<TT>(</TT><CODE>3</CODE><CODE>,</CODE><CODE> </CODE>Bcons<TT>(</TT><CODE>'='</CODE><CODE>,</CODE><CODE> </CODE>Acons<TT>(</TT><CODE>5</CODE><CODE>,</CODE><CODE> </CODE>Nil<TT>)</TT><TT>)</TT><TT>)</TT><TT>)</TT><TT>)</TT><CODE> </CODE>;;<BR><CODE>- : (int, char) list2 =</CODE><BR><CODE>Acons (2, Bcons ('+', Acons (3, Bcons ('=', Acons (...)))))</CODE><BR>

</PRE>
<BR>
<BR>
One can, obviously, instantiate the parameters <I>'a</I> and
<I>'b</I> with the same type.


<PRE><BR># Acons<TT>(</TT><CODE>1</CODE><CODE>,</CODE><CODE> </CODE>Bcons<TT>(</TT><CODE>2</CODE><CODE>,</CODE><CODE> </CODE>Acons<TT>(</TT><CODE>3</CODE><CODE>,</CODE><CODE> </CODE>Bcons<TT>(</TT><CODE>4</CODE><CODE>,</CODE><CODE> </CODE>Nil<TT>)</TT><TT>)</TT><TT>)</TT><TT>)</TT><CODE> </CODE>;;<BR><CODE>- : (int, int) list2 = Acons (1, Bcons (2, Acons (3, Bcons (4, Nil))))</CODE><BR>

</PRE>
<BR>
<BR>
This use of the type <I>list2</I> can, as in the preceding example, serve
to mark even integers and odd integers. In this way we extract the sublist
of even integers in order to construct an ordinary list.


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>extract_odd<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Nil<CODE> </CODE>-&gt;<CODE> </CODE>[]<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Acons<TT>(</TT><CODE>_,</CODE><CODE> </CODE>x<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE>extract_odd<CODE> </CODE>x<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Bcons<TT>(</TT>n<CODE>,</CODE><CODE> </CODE>x<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE>n::<TT>(</TT>extract_odd<CODE> </CODE>x<TT>)</TT><CODE> </CODE>;;<BR><CODE>val extract_odd : ('a, 'b) list2 -&gt; 'b list = &lt;fun&gt;</CODE><BR>

</PRE>

The definition of this function doesn't give a single clue as to the nature
of the values stored in the structure. That is why its type is
parameterized.<BR>
<BR>
<A NAME="toc20"></A>
<H3> Scope of declarations</H3>
<A NAME="@concepts85"></A>
Constructor names obey the same scope discipline as global declarations: a
redefinition masks the previous one. Nevertheless values of the masked
type still exist. The interactive toplevel does not distinguish these two
types in its output. Whence some unclear error messages.<BR>
<BR>
In this first example, the constant constructor <TT>Nil</TT> of type
<I>int_or_char</I> has been masked by the constructor declarations of
the type <I>('a, 'b) list2</I>.


<PRE><BR># Int_cons<TT>(</TT><CODE>0</CODE><CODE>,</CODE><CODE> </CODE>Nil<TT>)</TT><CODE> </CODE>;;<BR><CODE>Characters 13-16:</CODE><BR><CODE>This expression has type ('a, 'b) list2 but is here used with type</CODE><BR><CODE>  int_or_char_list</CODE><BR>

</PRE>
<BR>
<BR>
This second example provokes a rather baffling error message, at least the
first time it appears. Let the little program be as follows:


<PRE><BR># <B>type</B><CODE> </CODE>t1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Empty<CODE> </CODE><CODE>|</CODE><CODE> </CODE>Full;;<BR><CODE>type t1 = | Empty | Full</CODE><BR># <B>let</B><CODE> </CODE>empty_t1<CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>x<CODE> </CODE><B>with</B><CODE> </CODE>Empty<CODE> </CODE>-&gt;<CODE> </CODE><B>true</B><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Full<CODE> </CODE>-&gt;<CODE> </CODE><B>false</B><CODE> </CODE>;;<BR><CODE>val empty_t1 : t1 -&gt; bool = &lt;fun&gt;</CODE><BR># empty_t1<CODE> </CODE>Empty;;<BR><CODE>- : bool = true</CODE><BR>

</PRE>
<BR>
<BR>
Then, we redeclare the type <I>t1</I>:


<PRE><BR># <B>type</B><CODE> </CODE>t1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{u<CODE> </CODE><CODE>:</CODE><CODE> </CODE>int;<CODE> </CODE>v<CODE> </CODE><CODE>:</CODE><CODE> </CODE>int}<CODE> </CODE>;;<BR><CODE>type t1 = { u: int; v: int }</CODE><BR># <B>let</B><CODE> </CODE>y<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>u<CODE>=</CODE><CODE>2</CODE>;<CODE> </CODE>v<CODE>=</CODE><CODE>3</CODE><CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>val y : t1 = {u=2; v=3}</CODE><BR>

</PRE>
<BR>
<BR>
Now if we apply the function <TT>empty_t1</TT> to a value of the new type
<I>t1</I>, we get the following error message:


<PRE><BR># empty_t1<CODE> </CODE>y;;<BR><CODE>Characters 10-11:</CODE><BR><CODE>This expression has type t1 but is here used with type t1</CODE><BR>

</PRE>

The first occurrence of <I>t1</I> represents the first type defined, while
the second corresponds to the second type. <BR>
<BR>
<A NAME="toc21"></A>
<H3> Function types</H3>
<A NAME="@concepts86"></A>
The type of the argument of a constructor may be arbitrary. In particular,
it may very well contain a function type. The following type constructs
lists, all of whose elements except the last are function values.


<PRE><BR># <B>type</B><CODE> </CODE><I>'a</I><CODE> </CODE>listf<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Val<CODE> </CODE><B>of</B><CODE> </CODE><I>'a</I><BR><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Fun<CODE> </CODE><B>of</B><CODE> </CODE><TT>(</TT><I>'a</I><CODE> </CODE>-&gt;<CODE> </CODE><I>'a</I><TT>)</TT><CODE> </CODE><CODE>*</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>listf<CODE> </CODE>;;<BR><CODE>type 'a listf = | Val of 'a | Fun of ('a -&gt; 'a) * 'a listf</CODE><BR>

</PRE>
<BR>
<BR>
Since function values are values which can be manipulated in the language,
we can construct values of type <I>listf</I>:


<PRE><BR># <B>let</B><CODE> </CODE>eight_div<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT><CODE>/</CODE><TT>)</TT><CODE> </CODE><CODE>8</CODE><CODE> </CODE>;;<BR><CODE>val eight_div : int -&gt; int = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>gl<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Fun<CODE> </CODE><TT>(</TT>succ<CODE>,</CODE><CODE> </CODE><TT>(</TT>Fun<CODE> </CODE><TT>(</TT>eight_div<CODE>,</CODE><CODE> </CODE>Val<CODE> </CODE><CODE>4</CODE><TT>)</TT><TT>)</TT><TT>)</TT><CODE> </CODE>;;<BR><CODE>val gl : int listf = Fun (&lt;fun&gt;, Fun (&lt;fun&gt;, Val 4))</CODE><BR>

</PRE>

and functions which pattern-match such values:


<PRE>
<CODE> </CODE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>compute<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Val<CODE> </CODE>v<CODE> </CODE>-&gt;<CODE> </CODE>v<BR><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Fun<TT>(</TT>f<CODE>,</CODE><CODE> </CODE>x<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE>f<CODE> </CODE><TT>(</TT>compute<CODE> </CODE>x<TT>)</TT><CODE> </CODE>;;<BR><CODE>val compute : 'a listf -&gt; 'a = &lt;fun&gt;</CODE><BR># compute<CODE> </CODE>gl;;<BR><CODE>- : int = 3</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc22"></A>
<H3> Example: representing trees</H3>
<A NAME="@concepts87"></A>
<A NAME="ex-arbre-fn"></A>
Tree structures come up frequently in programming. Recursive types make it
easy to define and manipulate such structures. In this subsection, we give two
examples of tree structures.<BR>
<BR>

<H5> Binary trees</H5><A NAME="par-arbre-bin"></A> 
We define a binary tree structure whose nodes are labelled with values of a
single type by declaring:


<PRE><BR># <B>type</B><CODE> </CODE><I>'a</I><CODE> </CODE>bin_tree<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Empty<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Node<CODE> </CODE><B>of</B><CODE> </CODE><I>'a</I><CODE> </CODE>bin_tree<CODE> </CODE><CODE>*</CODE><CODE> </CODE><I>'a</I><CODE> </CODE><CODE>*</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>bin_tree<CODE> </CODE>;;<BR>

</PRE>
<BR>
<BR>
We use this structure to define a little sorting program using binary
search trees. A binary search tree has the property that all the values in
the left branch are less than that of the root, and all those of the right
branch are greater. Figure <A HREF="book-ora016.html#fig-arbin">2.5</A> gives an example of such a
structure over the integers. The empty nodes (constructor <TT>Empty</TT>)
are represented there by little squares; the others (constructor
<TT>Node</TT>), by a circle in which is inscribed the stored value.<BR>
<BR>
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora002.gif"> <BR>
<BR>
<DIV ALIGN=center>Figure 2.5: Binary search tree.</DIV><BR>

<A NAME="fig-arbin"></A>
</DIV>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>A sorted list is extracted from a binary search tree via an inorder
traversal carried out by the following function:<BR>
<BR>


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>list_of_tree<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Empty<CODE> </CODE>-&gt;<CODE> </CODE>[]<BR><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Node<TT>(</TT>lb<CODE>,</CODE><CODE> </CODE>r<CODE>,</CODE><CODE> </CODE>rb<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT>list_of_tree<CODE> </CODE>lb<TT>)</TT><CODE> </CODE><CODE>@</CODE><CODE> </CODE><TT>(</TT>r<CODE> </CODE>::<CODE> </CODE><TT>(</TT>list_of_tree<CODE> </CODE>rb<TT>)</TT><TT>)</TT><CODE> </CODE>;;<BR><CODE>val list_of_tree : 'a bin_tree -&gt; 'a list = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
To obtain a binary search tree from a list, we define an insert function.


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>insert<CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Empty<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Node<TT>(</TT>Empty<CODE>,</CODE><CODE> </CODE>x<CODE>,</CODE><CODE> </CODE>Empty<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Node<TT>(</TT>lb<CODE>,</CODE><CODE> </CODE>r<CODE>,</CODE><CODE> </CODE>rb<TT>)</TT><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>x<CODE> </CODE><CODE>&lt;</CODE><CODE> </CODE>r<CODE> </CODE><B>then</B><CODE> </CODE>Node<TT>(</TT>insert<CODE> </CODE>x<CODE> </CODE>lb<CODE>,</CODE><CODE> </CODE>r<CODE>,</CODE><CODE> </CODE>rb<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>Node<TT>(</TT>lb<CODE>,</CODE><CODE> </CODE>r<CODE>,</CODE><CODE> </CODE>insert<CODE> </CODE>x<CODE> </CODE>rb<TT>)</TT><CODE> </CODE>;;<BR><CODE>val insert : 'a -&gt; 'a bin_tree -&gt; 'a bin_tree = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The function to transform a list into a tree is obtained by iterating the
function <TT>insert</TT>.


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>tree_of_list<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Empty<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>h::t<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>insert<CODE> </CODE>h<CODE> </CODE><TT>(</TT>tree_of_list<CODE> </CODE>t<TT>)</TT><CODE> </CODE><CODE> </CODE>;;<BR><CODE>val tree_of_list : 'a list -&gt; 'a bin_tree = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The sort function is then simply the composition of the functions
<TT>tree_of_list</TT> and <TT>list_of_tree</TT>.


<PRE><BR># <B>let</B><CODE> </CODE>sort<CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>list_of_tree<CODE> </CODE><TT>(</TT>tree_of_list<CODE> </CODE>x<TT>)</TT><CODE> </CODE>;;<BR><CODE>val sort : 'a list -&gt; 'a list = &lt;fun&gt;</CODE><BR># sort<CODE> </CODE><CODE>[</CODE><CODE>5</CODE>;<CODE> </CODE><CODE>8</CODE>;<CODE> </CODE><CODE>2</CODE>;<CODE> </CODE><CODE>7</CODE>;<CODE> </CODE><CODE>1</CODE>;<CODE> </CODE><CODE>0</CODE>;<CODE> </CODE><CODE>3</CODE>;<CODE> </CODE><CODE>6</CODE>;<CODE> </CODE><CODE>9</CODE>;<CODE> </CODE><CODE>4</CODE><CODE>]</CODE><CODE> </CODE>;;<BR><CODE>- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]</CODE><BR>

</PRE>
<BR>
<BR>

<H5> General planar trees</H5>
<A NAME="@fonctions85"></A>
<A NAME="@fonctions86"></A>
<A NAME="@fonctions87"></A>
In this part, we use the following predefined functions from the
<TT>List</TT> module (see page <A HREF="book-ora076.html#sec-mod-list">??</A>):
<UL>
<LI>
 <TT>List.map</TT>: which applies a function to all the elements of a
list and returns the list of results;

<LI> <TT>List.fold_left</TT>: which is an equivalent version of the
function <TT>fold_left</TT> defined on page <A HREF="book-ora015.html#fun-fold-left">??</A>; 

<LI> <TT>List.exists</TT>: which applies a boolean-valued function to all
the elements of a list; if one of these applications yields <TT>true</TT>
then the result is <TT>true</TT>, otherwise the function returns
<TT>false</TT>.
</UL>
A general planar tree is a tree whose number of branches is not
fixed a priori; to each node is associated a list of branches whose
length may vary.


<PRE><BR># <B>type</B><CODE> </CODE><I>'a</I><CODE> </CODE>tree<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Empty<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Node<CODE> </CODE><B>of</B><CODE> </CODE><I>'a</I><CODE> </CODE><CODE>*</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>tree<CODE> </CODE>list<CODE> </CODE>;;<BR>

</PRE>

The empty tree is represented by the value <EM>Empty</EM>. A leaf is a node
without branches either of the form <EM>Node(x,[])</EM>, or of the
degenerate form <EM>Node(x, [Empty;Empty; ..])</EM>. It is then relatively
easy to write functions to manipulate these trees, e.g., to determine
whether an element belongs to a tree or compute the height of the tree.<BR>
<BR>
To test membership of an element <EM>e</EM>, we use the following
algorithm: if the tree is empty then <EM>e</EM> does not belong to this
tree, otherwise <EM>e</EM> belongs to the tree if and only if either it is
equal to the label of the root, or it belongs to one of its branches.


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>belongs<CODE> </CODE>e<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Empty<CODE> </CODE>-&gt;<CODE> </CODE><B>false</B><BR><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Node<TT>(</TT>v<CODE>,</CODE><CODE> </CODE>bs<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT>e<CODE>=</CODE>v<TT>)</TT><CODE> </CODE><B>or</B><CODE> </CODE><TT>(</TT>List.exists<CODE> </CODE><TT>(</TT>belongs<CODE> </CODE>e<TT>)</TT><CODE> </CODE>bs<TT>)</TT><CODE> </CODE>;;<BR><CODE>val belongs : 'a -&gt; 'a tree -&gt; bool = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
To compute the height of a tree, we use the following definition: an empty
tree has height <EM>0</EM>, otherwise the height of the tree is equal to
the height of its highest subtree plus <EM>1</EM>. 


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>height<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>max_list<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE>List.fold_left<CODE> </CODE>max<CODE> </CODE><CODE>0</CODE><CODE> </CODE>l<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>function</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Empty<CODE> </CODE>-&gt;<CODE> </CODE><CODE>0</CODE><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Node<CODE> </CODE><TT>(</TT><CODE>_,</CODE><CODE> </CODE>bs<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE>1</CODE><CODE> </CODE><CODE>+</CODE><CODE> </CODE><TT>(</TT>max_list<CODE> </CODE><TT>(</TT>List.map<CODE> </CODE>height<CODE> </CODE>bs<TT>)</TT><TT>)</TT><CODE> </CODE>;;<BR><CODE>val height : 'a tree -&gt; int = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc23"></A>
<H3> Recursive values which are not functions</H3>
<A NAME="decl_rec"></A>
Recursive declaration of non-function values allows the construction of
circular data structures.<BR>
<BR>
The following declaration constructs a circular list with one element.


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>1</CODE>::l<CODE> </CODE>;;<BR><CODE>val l : int list =</CODE><BR><CODE>  [1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; ...]</CODE><BR>

</PRE>
<BR>
<BR>
Application of a recursive function to such a list risks looping until
memory overflows.


<PRE><BR># size<CODE> </CODE>l<CODE> </CODE>;;<BR><CODE>Stack overflow during evaluation (looping recursion?).</CODE><BR>

</PRE>
<BR>
<BR>
Structural equality remains usable with such lists only when physical
equality is first verified:


<PRE><BR># l<CODE>=</CODE>l<CODE> </CODE>;;<BR><CODE>- : bool = true</CODE><BR>

</PRE>
<BR>
<BR>
In short, if you define a new list, even an equal one, you must not use the
structural equality test on pain of seeing your program loop indefinitely.
So we don't recommend attempting to evaluate the following example:
<PRE>
let rec l2 = 1::l2 in l=l2 ;;
</PRE>On the other hand, physical equality always remains possible.


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>l2<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>1</CODE>::l2<CODE> </CODE><B>in</B><CODE> </CODE>l<CODE>==</CODE>l2<CODE> </CODE>;;<BR><CODE>- : bool = false</CODE><BR>

</PRE>
<BR>
<BR>
The predicate <TT>==</TT> tests equality of an immediate value or sharing
of a structured object (equality of the address of the value). We will use
it to verify that in traversing a list we don't retraverse a sublist which
was already examined. First of all, we define the function <TT>memq</TT>,
which verifies the presence of an element in the list by relying on
physical equality. It is the counterpart to the function <TT>mem</TT>
which tests structural equality; these two functions belong to the module
<TT>List</TT>.
<A NAME="@fonctions88"></A>
<A NAME="@fonctions89"></A>


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>memq<CODE> </CODE>a<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>l<CODE> </CODE><B>with</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE><B>false</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>b::l<CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT>a<CODE>==</CODE>b<TT>)</TT><CODE> </CODE><B>or</B><CODE> </CODE><TT>(</TT>memq<CODE> </CODE>a<CODE> </CODE>l<TT>)</TT><CODE> </CODE>;;<BR><CODE>val memq : 'a -&gt; 'a list -&gt; bool = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The size computation function is redefined, storing the list of lists
already examined and halting if a list is encountered a second time.


<PRE><BR># <B>let</B><CODE> </CODE>special_size<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>size_aux<CODE> </CODE>previous<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>l<CODE> </CODE><B>with</B><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE><CODE>0</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE><CODE>_::</CODE>l1<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>if</B><CODE> </CODE>memq<CODE> </CODE><CODE> </CODE>l<CODE> </CODE>previous<CODE> </CODE><B>then</B><CODE> </CODE><CODE>0</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><CODE>1</CODE><CODE> </CODE><CODE>+</CODE><CODE> </CODE><TT>(</TT>size_aux<CODE> </CODE><TT>(</TT>l::previous<TT>)</TT><CODE> </CODE>l1<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>size_aux<CODE> </CODE>[]<CODE> </CODE>l<CODE> </CODE>;;<BR><CODE>val special_size : 'a list -&gt; int = &lt;fun&gt;</CODE><BR># special_size<CODE> </CODE><CODE>[</CODE><CODE>1</CODE>;<CODE>2</CODE>;<CODE>3</CODE>;<CODE>4</CODE><CODE>]</CODE><CODE> </CODE>;;<BR><CODE>- : int = 4</CODE><BR># special_size<CODE> </CODE>l<CODE> </CODE>;;<BR><CODE>- : int = 1</CODE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>l1<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>1</CODE>::<CODE>2</CODE>::l2<CODE> </CODE><CODE> </CODE><B>and</B><CODE> </CODE><CODE> </CODE>l2<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>1</CODE>::<CODE>2</CODE>::l1<CODE> </CODE><B>in</B><CODE> </CODE>special_size<CODE> </CODE>l1<CODE> </CODE>;;<BR><CODE>- : int = 4</CODE><BR>

</PRE>
<BR>
<BR>
<HR>
<A HREF="book-ora015.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora017.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
